package com.leetcode.根据数据结构分类.数组;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: ZhouBert
 * @date: 2021/1/18
 * @description: 169. 多数元素
 * https://leetcode-cn.com/problems/majority-element/
 */
public class A_169_多数元素 {

	public static void main(String[] args) {
		int[] nums = new int[]{3, 2, 3};
		nums = new int[]{2, 2, 1, 1, 1, 2, 2};
		//nums = new int[]{10, 9, 8, 7, 6, 2, 1};
		A_169_多数元素 action = new A_169_多数元素();
		//int res = action.majorityElementMine(nums);
		int res = action.majorityElementBySort(nums);
		System.out.println("res = " + res);
	}

	/**
	 * 虽然给了 位运算，分治的标签，但是还是没有该思路。
	 *
	 * @param nums
	 * @return
	 */
	public int majorityElementMine(int[] nums) {
		//统计数量
		HashMap<Integer, Integer> map = new HashMap<>();
		int len = nums.length;
		int value = 0;
		for (int i = 0; i < len; i++) {
			value = nums[i];
			if (map.containsKey(value)) {
				map.put(value, map.get(value) + 1);
			} else {
				map.put(value, 1);
			}
		}
		//莫非这就是 位运算
		int size = len >> 1;
		int res = 0;
		//遍历统计
		for (Map.Entry<Integer, Integer> item :
				map.entrySet()) {
			if (item.getValue() > size) {
				res = item.getKey();
				break;
			}
		}
		return res;
	}


	/**
	 * 这个比较巧妙了
	 * --
	 * 1.先进行排序；
	 * 2.在 length/2 的位置的值就是众数
	 * --
	 * 要求 O(1) 的空间复杂度
	 * 通过堆排序，确实是快了一些。重温了下堆排序。
	 * @param nums
	 * @return
	 */
	public int majorityElementBySort(int[] nums) {
		int len = nums.length;
		//原地建堆
		heapify(nums, len);
		//堆排序
		heapSort(nums, len);
		return nums[len >> 1];
	}

	/**
	 * 其实真正符合要求的只有这一个算法。
	 * 这个算法更加巧妙了
	 * --
	 * 投票算法：
	 * 1.原理：如果把 众数当作1，其他数当作 -1，那么遍历一遍和>0
	 *  【当 候选人和非候选人投票相等时，接下来的一票就是候选人！】
	 * @param nums
	 * @return
	 */
	public int majorityElementByVote(int[] nums){
		int count = 0;
		Integer candidate = null;
		int len = nums.length;
		for (int i = 0; i < len; i++) {
			if (count==0){
				candidate=nums[i];
			}
			count += (nums[i] == candidate) ? 1 : -1;
		}
		return candidate;
	}

	/**
	 * 将数组进行堆排序
	 *
	 * @param nums
	 * @param len
	 */
	private void heapSort(int[] nums, int len) {
		int lastIndex = len - 1;
		while (lastIndex >= 0) {
			swap(nums, 0, lastIndex);
			shiftDown(0, nums, lastIndex--);
		}
	}

	private void heapify(int[] nums, int len) {
		for (int i = getParent(len - 1); i >= 0; i--) {
			shiftDown(i, nums, len);
		}
	}

	/**
	 * 将元素进行下滤
	 * （建成大顶堆）-> 为了最后的从小到大排序
	 *
	 * @param index
	 * @param nums
	 * @param len   数组的长度
	 */
	private void shiftDown(int index, int[] nums, int len) {
		int leftIndex = getLeftChild(index);
		int rightIndex = leftIndex + 1;
		int swapIndex = 0;
		while (rightIndex < len) {
			//找到最大的索引
			swapIndex = nums[leftIndex] > nums[rightIndex] ? leftIndex : rightIndex;
			if (nums[index] < nums[swapIndex]) {
				swap(nums, index, swapIndex);

				index = swapIndex;
				leftIndex = getLeftChild(index);
				rightIndex = leftIndex + 1;
			} else {
				break;
			}
		}
		if (rightIndex == len) {
			swapIndex = leftIndex;
			//此时 leftIndex 存在
			//仍然需要进行比较
			if (nums[index] < nums[swapIndex]) {
				swap(nums, index, swapIndex);
			}
		}
	}

	/**
	 * 交换 index 和 swapIndex 的值
	 *
	 * @param nums
	 * @param index
	 * @param swapIndex
	 */
	private void swap(int[] nums, int index, int swapIndex) {
		int tempValue = nums[index];
		nums[index] = nums[swapIndex];
		nums[swapIndex] = tempValue;
	}

	/**
	 * 获取 index 的 parent 坐标
	 *
	 * @param index
	 * @return
	 */
	private int getParent(int index) {
		return (index - 1) >> 1;
	}

	private int getLeftChild(int index) {
		return (index << 1) + 1;
	}


}
